package com.example.graph;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

/**
 * 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。
 *  在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
 * 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
 *
 *  示例 1：
 *  输入：["a==b","b!=a"]
 * 输出：false
 * 解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
 *
 *  示例 2：
 *  输入：["b==a","a==b"]
 * 输出：true
 * 解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
 *
 *  示例 3：
 *  输入：["a==b","b==c","a==c"]
 * 输出：true
 *
 *  示例 4：
 *  输入：["a==b","b!=c","c==a"]
 * 输出：false
 *
 *  示例 5：
 *  输入：["c==c","b==d","x!=z"]
 * 输出：true
 */
public class Leetcode990_EquationPossible {
    public static void main(String[] args) {
        String[] equations = {"b==b", "b==e", "e==c", "d!=e"};
        System.out.println(new Solution().equationsPossible(equations));
    }

    static class Solution {
        /**
         * 并查集
         * 由于等号具有传递性，可以先遍历 equations 将等号的全部变量全部归到一个"集合"中
         * 然后再次遍历整个 equations 查看 不等的两个变量的"父节点"是否是同一个，如果是同一个就返回false
         * @param equations
         * @return
         */
        private boolean equationsPossible1(String[] equations) {
            UnionFindSet uf = new UnionFindSet();
            for (String equation : equations) {
                if (equation.charAt(1) == '=') {
                    int node1 = equation.charAt(0) - 'a';
                    int node2 = equation.charAt(3) - 'a';
                    uf.union(node1, node2);
                }
            }

            for (String equation : equations) {
                if (equation.charAt(1) == '!') {
                    int node1 = equation.charAt(0) - 'a';
                    int node2 = equation.charAt(3) - 'a';
                    if (uf.find(node1) == uf.find(node2)) return false;
                }
            }
            return true;
        }

        public boolean equationsPossible(String[] equations) {

            return equationsPossible1(equations);
        }

        class UnionFindSet {
            int[] parents;// 小写字母的顺序

            public UnionFindSet() {
                this.parents = new int[26];
                for (int i = 0; i < parents.length; i++) {
                    parents[i] = i;
                }
            }

            public int find(int node) {
                if (parents[node] != node)
                    parents[node] = find(parents[node]);
                return parents[node];
            }

            public void union(int node1, int node2) {
                int p1 = find(node1);
                int p2 = find(node2);
                if (p1 != p2) {
                    parents[p2] = p1;
                }
            }
        }
    }
}
